package leetcode每日一题;

import java.util.*;

/**
 * 1. 问题描述
 *      在一个由小写字母构成的字符串 s 中，包含由一些连续的相同字符所构成的分组。
 *      例如，在字符串 s = "abbxxxxzyy"中，就含有 "a", "bb", "xxxx", "z" 和 "yy" 这样的一些分组。
 *      分组可以用区间 [start, end] 表示，其中 start 和 end 分别表示该分组的起始和终止位置的下标。
 *      上例中的 "xxxx" 分组用区间表示为 [3,6] 。
 *      我们称所有包含大于或等于三个连续字符的分组为 较大分组 。
 *      找到每一个 较大分组 的区间，按起始位置下标递增顺序排序后，返回结果。
 *
 * 2. 算法分析
 *      1. 暴力法
 *
 *      优化
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 分组较大的位置 {
    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(5);
        for (Integer integer : list) {
            System.out.println(integer);
        }
    }

    public static boolean isThree(int num) {
        return true;
    }

    /**
     * 暴力法   效率比较低
     * @param s
     * @return
     */
    public static List<List<Integer>> largeGroupPositions1(String s) {
        List<List<Integer>> ans = new ArrayList<>(); // 记录结果
        for(int i = 0; i < s.length(); i++) {
            int j = i; // 从当前字符开始扫描后面的，判断当前字符是否连续出现了至少3次
            int count = 0;
            while(j < s.length() && s.charAt(j) == s.charAt(i)) {
                j++;
                count++;
            }
            if(count >= 3) {
                List<Integer> temp = new ArrayList<>();
                temp.add(i);
                temp.add(j-1);
                ans.add(temp);
            }
            i = j - 1;
        }
        return ans;
    }

    /**
     * 与上面的算法相同，但是效率高很多，查看jdk源码发现s.charAt()的底层，每次调用都需要将s转换为数组，所以在下面的代码中
     * 先将s转换为字符数组，只需要转化一次，所以效率就高了
     * @param s
     * @return
     */
    public static List<List<Integer>> largeGroupPositions2(String s) {
        List<List<Integer>> ans = new ArrayList<>(); // 记录结果
        final char[] sarr = s.toCharArray();
        for(int i = 0; i < sarr.length; i++) {
            int j = i; // 从当前字符开始扫描后面的，判断当前字符是否连续出现了至少3次
            int count = 0;
            while(j < sarr.length && sarr[j] == sarr[i]) {
                j++;
                count++;
            }
            if(count >= 3) {
                List<Integer> temp = new ArrayList<>();
                temp.add(i);
                temp.add(j-1);
                ans.add(temp);
            }
            i = j - 1;
        }
        return ans;
    }

    /**
     * 设置一个计数器记录当前字符连续出现的次数，每次找完一个字符的连续出现次数之后，重置为1
     * 继续下一轮计数    效率也比较高
     * @param s
     * @return
     */
    public static List<List<Integer>> largeGroupPositions3(String s) {
        List<List<Integer>> ans = new ArrayList<>();
        int count = 1; // 记录当前字符连续出现的次数，注意每次找完当前字符的连续出现次数之后需要更新为1
        int len = s.length();
        char[] sarr = s.toCharArray();
        for(int i = 0; i < len; i++) {
            if(i == len -1 || sarr[i] != sarr[i+1]) {
                // 判断当前count是否大于等于3
                if(count >= 3) {
                    // 当前末尾索引为i，数量为count，则其实索引为x则 i - x + 1 = count --> x = i-count+1
                    ans.add(Arrays.asList(i-count+1,i));
                }
                count = 1; // 重置
            } else {
                count++;
            }
        }
        return ans;
    }
}
